Querying and searching information contained in XML documents that are stored within an object-relational database can be especially inefficient given certain queries. XML-aware indices, such as described in Chandrasekar, are available for providing quicker access to XML data in response to XPath queries. However, certain search operations are unable to effectively use XML indices, especially indices following a bottom-up evaluation of the XML document.
An XML index may be composed of a PATH table and a set of secondary indices on the PATH table. The PATH table contains one row per indexed node of an XML document. Each column of the table contains information associated with the indexed nodes, like the XPath or the value of the nodes; secondary indices can be built on the columns. An example of a secondary index is a b-tree index on the value column of the PATH table, also referred to as a value index. The XML index may be accessed when a user submits a query referencing one or more XML documents. The query can be decomposed in the manner described in Manikutty into expressions that use the PATH table. An optimization engine may evaluate an expression using a secondary index in lieu of evaluating directly from the PATH table.
A query that includes a value-based search is an example of a type of query that can be optimized by use of a secondary index. To search for a particular value within the XML document, a user may perform a linear search down the value column of the PATH table, performing as many comparisons as there are rows in the PATH table. Executing a search in this manner requires that each row is read from disk, a costly operation that should be minimized. Building a secondary index, like a b-tree index, on the value column would allow for index-based searching, thereby logarithmically reducing disk accesses for each search.
However, using a b-tree index that passes over most rows of the PATH table when searching for a value means that certain information would no longer be determined during course of a search. For example, if a user needs to ensure that an XPath is unique in an XML document while searching for a value, this can be easily determined when executing a linear search down the rows of a PATH table. On the other hand, it would be impossible to make this determination of a single-path occurrence in the course of a value-based search if most of the rows of the PATH table are passed over by use of a b-tree index.
Based on the foregoing, it would be desirable to be able to use an index, like a b-tree index, with such a single-path query, such that a correct determination could be made about the single-path occurrence while making use of the index optimization.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.